P6825 「EZEC-4」求和

i=1nj=1ngcd(i,j)i+j\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j}

d=1ni=1nj=1n[gcd(i,j)=d]di+j\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]d^{i+j}

d=1ni=1ndj=1nd[gcd(i,j)=1]d(i+j)d\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor } [\gcd(i,j)=1]d^{(i+j)d}

d=1nt=1ndμ(t)i=1ndtj=1ndtd(i+j)dt\sum_{d=1}^n \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{dt} \rfloor } d^{(i+j)dt}

d=1nt=1ndμ(t)(i=1ndtdidt)2\sum_{d=1}^n \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) (\sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor } d^{idt})^2

计算等比数列和时,需要递归计算。

#include <cstdio>

const int MAXN = 1.5e6; int Mod;

int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { if( x < 0 ) x += Mod; if( y < 0 ) y += Mod; return 1ll * x * y % Mod; }
int Squ( int x ) { return Mul( x , x ); }
int Quick_pow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = Squ( x ) ) if( po & 1 ) p = Mul( p , x ); return p; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return Mul( x , Inv( y ) ); }

int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve() {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) prime[ ++ prnum ] = i , mu[ i ] = -1;
		for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
}

int Sum( int a1 , int q , int n ) { //首项为a1,公比为q,项数为n
	if( n == 1 ) return a1;
	int haf = Sum( a1 , q , n / 2 ) , amid = Quick_pow( q , n / 2 );
	return Add( Mul( haf , amid + 1 ) , n & 1 ? Quick_pow( q , n ) : 0 );
}
int Solve( int n ) {
	int Ans = 0;
	for( int d = 1 ; d <= n ; d ++ ) {
		int q1 = Quick_pow( d , d );
		for( int j = 1 , q = q1 ; j <= n / d ; j ++ , q = Mul( q , q1 ) ) {
			if( d == 1 )
				Ans = Add( Ans , Mul( mu[ j ] , Squ( n / d / j ) ) );
			else
				Ans = Add( Ans , Mul( mu[ j ] , Squ( Sum( q , q , n / d / j ) ) ) );
		}
	}
	return ( Ans + Mod ) % Mod;
}

int T , n;
signed main( ) {
	sieve();
	scanf("%d",&T);
	while( T -- ) {
		scanf("%d %d",&n,&Mod);
		printf("%d\n", Solve( n ) );
	}
	return 0;
}

顺带一提,似乎式子可以继续化简,但不好计算。

T=1ndTdTμ(Td)(i=1nTdi)2\sum_{T=1}^n \sum_{d|T} d^T \mu(\frac{T}{d}) (\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor }d^{i})^2

T=1n(dTdTμ(Td)(1dTd1d)2)\sum_{T=1}^n \left( \sum_{d|T} d^T \mu(\frac{T}{d})(\frac{1-d^{\lfloor \frac{T}{d} \rfloor}}{1-d})^2 \right)